package com.leet.code.lcof;

import com.algorithm.model.TreeNode;
import com.algorithm.model.TreeNodeService;

import java.util.LinkedList;

public class Code28 {
    public static void main(String[] args) {
        TreeNode root = TreeNodeService.getTreeByArray(new int[]{1,2,2,3,4,4,3});
        System.out.println(new Code28().isSymmetric(root));

    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return false;
        }
        return judge(root.left, root.right);
    }

    public boolean judge(TreeNode l, TreeNode r) {
        if (l == null && r == null) {
            return true;
        }
        if (l == null || r == null) {
            return false;
        }
        return l.val == r.val && judge(l.left, r.right) && judge(l.right, r.left);
    }

    public boolean judge(LinkedList<TreeNode> list) {
        if (list == null || list.size() == 0) {
            return true;
        }
        LinkedList<TreeNode> tmp = new LinkedList<>();

        while (list.size() > 1) {
            TreeNode l = list.pollFirst();
            TreeNode r = list.pollLast();

            if (l.val != r.val) {
                return false;
            }
            tmp.addFirst(l.right);
            tmp.addFirst(l.left);
            tmp.addLast(r.left);
            tmp.addLast(r.right);
        }

        if (list.size() == 1) {
            return false;
        }

        return judge(tmp);

    }




}
